package com.swak.algs;

import com.swak.algs.node.TreeNode;

import lombok.Getter;
import lombok.Setter;
import lombok.ToString;
import lombok.experimental.Accessors;

/**
 * 是否平衡二叉树: 深度最大相差 1
 * 
 * @author lifeng
 */
public class Code10 {

	@Getter
	@Setter
	@Accessors(chain = true)
	@ToString
	static class Info {
		boolean bt;
		int deep;
	}

	static Info isBlanceTree(TreeNode head) {
		if (head == null) {
			return new Info().setBt(true).setDeep(0);
		}
		Info nodeInfo = new Info();
		Info leftInfo = isBlanceTree(head.left);
		Info rightInfo = isBlanceTree(head.right);
		nodeInfo.bt = leftInfo.bt & rightInfo.bt & (Math.abs(leftInfo.deep - rightInfo.deep) <= 1);
		nodeInfo.deep = Math.max(leftInfo.deep, rightInfo.deep) + 1;
		return nodeInfo;
	}

	public static void main(String[] args) {
		TreeNode root = TreeNode.newBlanceTree();
		System.out.println(isBlanceTree(root));
	}
}
